GATE CSE 2005
Q31.
Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s\inX and t\inY. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. The edge e must definitely belong to:Q32.
An undirected graph G has n nodes. Its adjacency matrix is given by an nxn square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are 1's. which one of the following is TRUE?Q33.
Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s\inX and t\inY. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?Q36.
Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:Q38.
What is the first order predicate calculus statement equivalent to the following? Every teacher is liked by some studentQ40.
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?